package com.wq.sort;

import java.io.IOException;

/**
 * @Author: wangqiang20995
 * @Date:2019/3/23
 * @Description:
 * @Resource:
 */
public class QuickSort extends BaseSort {
    public QuickSort(int size) {
        super(size);
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort(1000000);
//        System.out.println("base array");
//        quickSort.printArray(false);
//        System.out.println("----------------------------");
        long start = System.currentTimeMillis();
        quickSort.quickSort(0, quickSort.array.length - 1);
        long end = System.currentTimeMillis();
//        System.out.println("final array");
//        System.out.println("----------------------------");
//        quickSort.printArray(false);
        System.out.println("cost:" + (end - start));

    }

    private void quickSort(int low, int high) {
        if (low >= high) {
            return;
        }

        int first = array[low];
        int position = findPosition(low, high, first);
//        printArray(false);

        quickSort(low, position - 1);
        quickSort(position + 1, high);

    }

    private int findPosition(int start, int end, int value) {
        while (start < end) {
            while (start < end && (array[end] >= value)) {
                end--;
            }
            swap(start, end);

            while (start < end && (array[start] <= value)) {
                start++;
            }
            swap(start, end);
        }

        return start;
    }

    private void swap(int before, int after) {
        int temp = array[after];
        array[after] = array[before];
        array[before] = temp;
    }
}
